package org.gushi.datastruct.a05;


/**
 * 数组 循环双端队列的实现
 *
 * @param <E>
 */
public class CircleDeque<E> {

    private static final int DEFAULT_CAPACITY = 10;

    private int size;

    private int front = 0;

    public int getFront() {
        return front;
    }

    public void setFront(int front) {
        this.front = front;
    }

    public E[] elements;

    public E[] getElements() {
        return elements;
    }

    public void setElements(E[] elements) {
        this.elements = elements;
    }

    public CircleDeque() {
        elements = (E[]) new Object[DEFAULT_CAPACITY];
    }

    // 元素的数量
    public int size() {
        return size;
    }

    // 是否为空
    public boolean isEmpty() {
        return size <= 0;
    }

    // 清空
    public void clear() {
        size = 0;
        elements = null;
    }

    //入队  循环队列实现方式：数组不停的往后添加元素
    public void offer(E element) {
        ensureCapacity(size + 1);
        if (size == 0) {
            front = 0;
            elements[front] = element;
        } else {
            int position = (front + size) % elements.length;
            elements[position] = element;
        }
        size++;
    }

    //出队
    public E poll() {
        if (size <= 0) {
            return null;
        }
        E old = elements[front];
        elements[front] = null;
        size--;
        front = (front + 1) % elements.length;//必须要先加在取模，否则在最后和开始位置都有元素会有异常问题
        return old;
    }

    //查询队头的元素
    public E peek() {
        if (size <= 0) {
            return null;
        }
        return elements[front];
    }

    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;

        int newCapacity = oldCapacity + (oldCapacity >> 1);//后面一个*1.5 扩容为以前的1.5倍
        E[] newElements = (E[]) new Object[newCapacity];
        //此处存在线程安全问题的
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[(front + i) % elements.length];
        }
        front = 0;
        elements = newElements;
        System.out.println("旧容量：" + oldCapacity + "，新容量：" + newCapacity);
    }


    // 从队头出队
    public E deQueueFront() {
        if (size <= 0) {
            return null;
        }
        E old = elements[front];
        elements[front] = null;
        front = (front + 1) % elements.length;
        size--;
        return old;
    }

    // 从队头入队
    public void enQueueFront(E element) {
        ensureCapacity(size + 1);
        if (size <= 0) {
            elements[0] = element;
            front = 0;
        } else {
            if (front - 1 >= 0) {
                front = (front - 1) % elements.length;
            } else {
                front = (elements.length + front - 1) % elements.length;
            }
            elements[front] = element;
        }
        size++;
    }

    // 从队尾入队
    public void enQueueRear(E element) {
        ensureCapacity(size + 1);
        if (size <= 0) {
            elements[0] = element;
            front = 0;
        } else {
            front = (size + front) % elements.length;
            elements[front] = element;
        }
        size++;
    }

    // 从队尾出队
    public E deQueueRear() {
        if (size <= 0) {
            return null;
        }
        E old;
        if (front + size - 1 <= 0) {
            old = elements[(front + size - 1) % elements.length];
            elements[(front + size - 1) % elements.length] = null;
        } else {
            old = elements[(elements.length + front + size - 1) % elements.length];
            elements[(front + size - 1) % elements.length] = null;
        }
        size--;
        return old;
    }

    // 获取队列的头元素
    public E front() {
        if (size <= 0) {
            return null;
        }
        return elements[front];
    }

    // 获取队列的尾元素
    public E rear() {
        if (size <= 0) {
            return null;
        }
        return elements[(front + size - 1) % elements.length];
    }


}
